package leetcode;

/*
201. 数字范围按位与
给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
示例 1:
输入: [5,7]
输出: 4
示例 2:
输入: [0,1]
输出: 0
*/

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class problems_201 {
    public static void main(String[] args) {
        System.out.println(new Solution().rangeBitwiseAnd(9,12));
    }

    static class Solution {
        public int rangeBitwiseAnd(int m, int n) {
            int shift = 0; // 位移次数
            while (m<n){ // 同时进行位移，直到当 n和 m的大小关系变化，变成相等时停止
                m>>=1;
                n>>=1;
                shift++;
            }
            return m << shift;
        }
    }


    // 错误
//    static class Solution {
//        public int rangeBitwiseAnd(int m, int n) {
//            char[] strRet = Integer.toBinaryString(n).toCharArray();
//            if (n > m) for (int i = 0; i < Integer.toBinaryString(n-m).length(); i++) {
//                strRet[strRet.length - 1 - i] = '0';
//            }
//            return Integer.parseInt(new String(strRet),2);
//        }
//    }
}